leetcode/100-n/115. 不同的子序列.md

算法正确，但性能低下，递归待优化

package main

import (
    "fmt"
)

func main(){
    // s := "rabbbit"
    s := "adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc"
    // t := "rabbit"
    t := "bcddceeeebecbc"
    ret := numDistinct(s,t)
    fmt.Println(ret)
}

var sLen int
var tLen int

var ss string
var ts string
func numDistinct(s string, t string) int {
    sLen = len(s)
    tLen = len(t)
    if s == "" || sLen < tLen{
        return 0
    }
    ss = s
    ts = t
    return dp(0,0)
}
func dp(si int, ti int) int {
    count := 0
    // 寻找第一个相同得字母
    for {
        //递归点
        if ti == tLen {
            return count + 1
        }
        //递归点
        if sLen - si == tLen - ti {
            if ss[si:] == ts[ti:] {
                return count + 1
            } else {
                return count
            }
        }
        // fmt.Printf("si:%d, ti:%d\n", si, ti)
        if ss[si] == ts[ti] {
            // case 1 要
            count += dp(si + 1, ti + 1)
            // case 2 不要
            // break
        }
        si++
    }
    return count
}